package com.lun.swordtowardoffer2.c01;

public class AddBinary {
	public String addBinary(String a, String b) {
		StringBuilder sb = new StringBuilder();
		
		int ai = a.length() - 1, bi = b.length() - 1, carry = 0;
		
		while(ai >= 0 || bi >= 0) {
			int aa = ai >= 0 ? a.charAt(ai--) - '0': 0;
			int bb = bi >= 0 ? b.charAt(bi--) - '0': 0;
			
			int sum = aa + bb + carry; 
			sb.append(sum & 1);
			carry = (sum >> 1) & 1;
		}
		
		if(carry == 1) {
			sb.append(carry);
		}
		return sb.reverse().toString();
	}
	
}
